1. Technical Field
The present invention relates to a configuration of a Field Programmable Gate Array (FPGA) to detect when rows or columns of a Hadamard matrix are received.
2. Related Art
Hadamard matrices are square matrices of 1's and −1's whose rows and columns are orthogonal. From this it follows that a Hadamard matrix, H, of size n satisfies the equation, HHT=nIn where In is the n×n identity matrix. Examples of Hadamard matrices of size n=4, 8 and 16 are shown in FIGS. 1-3. A necessary condition for the Hadamard matrix to exist is that n=1, 2 or a positive multiple of 4. A further condition is that a Hadamard matrix with n>2 exists only if rem(n,4)=0. In a Hadamard matrix, placing any two columns or rows side by side gives half the adjacent cells the same sign and half the other sign.
Hadamard matrices have applications in several different areas, including combinatorics, signal processing, and numerical analysis. Examples of the use of Hadamard matrices can be found relating to combinatorics in Ryser, H. J., Combinatorial Mathematics, John Wiley and Sons, 1963. Use of Hadamard matrices in signal processing can be found in Pratt, W. K., Digital Signal Processing, John Wiley and Sons, 1978. Hadamard matrices used in numerical analysis includes use in error-correction codes, in particular, the Reed-Muller error-correcting code.
A further use for Hadamard matrices is in a handshaking process for telecommunications. For instance, in a Third Generation “3G” Mobile telephone system, a mobile unit will transmit a particular row or signature in 3G terminology from a Hadamard 16 matrix that is recognized by the base station. This allows up to 16 mobile units to request servicing by the base station simultaneously. The particular row from the Hadamard matrix is transmitted a number of times to allow base station sufficient correlation gain in detecting the Hadamard matrix rows transmitted. The base station process of detecting a row or column is known as a random access channel (RACH) preamble detection.
The RACH preamble detection can be performed by correlation of rows or columns of the Hadamard matrix received with a Hadamard matrix stored in the base stations memory, or calculated by the base station. The base station can include a processor and memory to perform the correlation, or a logic device such as an FPGA that includes a number of internal logic blocks programmed to perform steps of the correlation calculation.
It is desirable to minimize the number of operation steps required to detect rows or columns of the Hadamard matrix to control the amount of processing or logic necessary for correlation in the base station. It is further desirable to minimize the number of clock cycles necessary to perform correlation to allow the base station time to respond to the mobile unit at least half way into the following access slot.